package style.Leetcode.初级算法.tree.tree_20220826_1_二叉树的最大深度;

import style.Leetcode.初级算法.tree.TreeNode;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * 二叉树的最大深度
 * <p>
 * 给定一个二叉树，找出其最大深度。
 * 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
 * 说明: 叶子节点是指没有子节点的节点。
 * <p>
 * 例子
 * 给定二叉树 [3,9,20,null,null,15,7]，
 * 返回它的最大深度 3 。
 */
public class Solution {
    /**
     * 思路一：递归算法处理
     */
    public int maxDepth1(TreeNode root) {
        return root == null ? 0 : Math.max(maxDepth1(root.left), maxDepth1(root.right)) + 1;
    }

    /**
     * 思路二：bfs  广度优先算法
     * <p>
     * BFS的实现原理就是一层层遍历，统计一下总共有多少层
     */
    public int maxDepth2(TreeNode root) {
        if (root == null) return 0;

        // 创建一个队列
        Deque<TreeNode> deque = new LinkedList<>();
        deque.push(root);
        int count = 0;
        while (!deque.isEmpty()) {
            int size = deque.size();
            while (size-- > 0) {
                TreeNode cur = deque.pop();
                if (cur.left != null)
                    deque.addLast(cur.left);
                if (cur.right != null)
                    deque.addLast(cur.right);
            }
            count++;
        }
        return count;
    }

    /**
     * 思路三：dfs 深度优先算法
     */
    public int maxDepth3(TreeNode root) {
        if (root == null) return 0;

        //stack记录的是节点，而level中的元素和stack中的元素
        //是同时入栈同时出栈，并且level记录的是节点在第几层
        Stack<TreeNode> stack = new Stack<>();
        Stack<Integer> level = new Stack<>();
        stack.push(root);
        level.push(1);
        int max = 0;
        while (!stack.isEmpty()) {
            //stack中的元素和level中的元素同时出栈
            TreeNode node = stack.pop();
            Integer temp = level.pop();
            max = Math.max(temp, max);
            if (node.left != null) {
                //同时入栈
                stack.push(node.left);
                level.push(temp+1);
            }
            if (node.right != null) {
                //同时入栈
                stack.push(node.right);
                level.push(temp+1);
            }
        }
        return max;
    }


    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(3);
        treeNode.left = new TreeNode(9);
        treeNode.left.left = null;
        treeNode.left.right = null;
        treeNode.right = new TreeNode(20);
        treeNode.right.left = new TreeNode(15);
        treeNode.right.left.left = null;
        treeNode.right.left.right = null;
        treeNode.right.right = new TreeNode(7);
        treeNode.right.right.left = null;
        treeNode.right.right.right = null;

        Solution solution = new Solution();
        System.out.println(solution.maxDepth1(treeNode));
        System.out.println(solution.maxDepth2(treeNode));
        System.out.println(solution.maxDepth3(treeNode));
    }

}
